package org.example;

import java.util.*;

// 广度优先算法
public class BFS {
    // 图的遍历算法其实就是多叉树的遍历算法加了个 visited 数组防止死循环；
    // 多叉树的遍历算法又是从二叉树遍历算法衍生出来的。
    // 所以我说 BFS 算法的本质就是二叉树的层序遍历。

    // 为啥BFS算法经常用来求解最短路径问题
    // 其实所谓的最短路径，都可以类比成二叉树最小深度这类问题（寻找距离根节点最近的叶子节点），递归遍历必须要遍历整棵树的所有节点才能找到目标节点，
    // 而层序遍历不需要遍历所有节点就能搞定，所以层序遍历适合解决这类最短路径问题。

    // 算法框架：
    // BFS的算法框架其实就是图结构的DFS/BFS遍历中给出的BFS遍历图结构的代码，共有三种写法
    // 对于实际的BFS算法问题，
    // 第一种写法最简单，但局限性太大，不常用；
    // 第二种写法最常用，中等难度的BFS算法题基本都可以用这种写法解决；
    // 第三种写法稍微复杂一点，但灵活性最高，可能会在一些难度较大的BFS问题中用到

    // BFS第二种写法
    static class BaseBFS {

        // 从s开始BFS遍历图的所有节点，且记录遍历的步数
        // 当走到目标节点target，返回步骤
//        public int bfs(int s, int target) {
//            boolean[] visited = new boolean[graph.size()];
//            Queue<Integer> queue = new LinkedList<>();
//            queue.offer(s);
//            visited[s] = true;
//            // 记录从s开始走到当前节点的步数
//            int step = 0;
//            while (!queue.isEmpty()) {
//                int sz = queue.size();
//                for (int i = 0; i < sz; i++) {
//                    int cur = queue.poll();
//                    System.out.println("visit " + cur + " at step " + step);
//                    // 判断是否到达终点
//                    if (cur == target) {
//                        return step;
//                    }
//                    // 将邻居节点加入队列，向四周扩散搜索
//                    for (int to : neighborsOf(cur)) {
//                        if (!visited[to]) {
//                            queue.offer(to);
//                            visited[to] = true;
//                        }
//                    }
//                }
//                step++;
//            }
//            // 如果走到这里，说明在途中没有找到目标节点
//            return -1;
//        }
    }

    // 773.滑动谜题
    // 力扣第 773 题「滑动谜题」就是一个可以运用 BFS 框架解决的题目，题目的要求如下：
    // 给你一个 2x3 的滑动拼图，用一个 2x3 的数组 board 表示。拼图中有数字 0~5 六个数，其中数字 0 就表示那个空着的格子，你可以移动其中的数字，当 board 变为 [[1,2,3],[4,5,0]] 时，赢得游戏。
    // 请你写一个算法，计算赢得游戏需要的最少移动次数，如果不能赢得游戏，返回 -1。
    // 比如说输入的二维数组 board = [[4,1,2],[5,0,3]]，算法应该返回 5：

    // 其实棋盘的初始状态就可以认为是起点：
    // [[2,4,1],
    // [5,0,3]]
    // 我们最终的目标状态是把棋盘变成这样：
    // [[1,2,3],
    // [4,5,0]]
    // 对于这道题，我们抽象出来的图结构也是会包含环的，所以需要一个 visited 数组记录已经走过的节点，避免成环导致死循环。
    // 比如说我从 [[2,4,1],[5,0,3]] 节点开始，数字 0 向右移动得到新节点 [[2,4,1],[5,3,0]]，但是这个新节点中的 0 也可以向左移动的，
    // 又会回到 [[2,4,1],[5,0,3]]，这其实就是成环。我们也需要一个 visited 哈希集合来记录已经走过的节点，防止成环导致的死循环。
    // 其中比较有技巧性的点在于，二维数组有[上下左右]的概念，压缩成一堆的字符串后，还怎么把数字0和上下左右的数字进行交换？

    // 对于这道题，题目说输入数组大小都是2x3，所以我们可以直接手动写出来这个映射
    /*
     * 二维数组
     * [2,4,1]
     * [5,0,3]
     *
     * 一维数组
     *       [2,4,1,5,0,3]
     * 下标为  0 1 2 3 4 5
     *
     * 记录一维字符串的相邻索引
     * int[][] neighbor = new int[][]{
     *   {1,3},    // 表示二维数组中的元素2, 在二维数组的相邻值为：{4,5}，在一维数组中对应的下标为：{1,3}
     *   {0,4,2},  // 表示二维数组中的元素4, 在二维数组的相邻值为：{2,0,1}，在一维数组中对应的下标为：{0,4,2}
     *   {1,5},    // 表示二维数组中的元素1, 在二维数组的相邻值为：{4,3}，在一维数组中对应的下标为：{1,5}
     *   {0,4},    // 表示二维数组中的元素5, 在二维数组的相邻值为：{2,0}，在一维数组中对应的下标为：{0,4}
     *   {3,1,5},  // 表示二维数组中的元素0, 在二维数组的相邻值为：{5,4,3}，在一维数组中对应的下标为：{3,1,5}
     *   {4,2}     // 表示二维数组中的元素3, 在二维数组的相邻值为：{4,3}，在一维数组中对应的下标为：{4,2}
     * }
     * */

    // 如果是 m x n 的二维数组，怎么办？
    // 对于一个 m x n 的二维数组，手写它的一维索引映射肯定不现实了，需要用代码生成它的一维索引映射。
    // 观察上图就能发现，如果二维数组中的某个元素 e 在一维数组中的索引为 i，
    // 那么 e 的左右相邻元素在一维数组中的索引就是 i - 1 和 i + 1，而 e 的上下相邻元素在一维数组中的索引就是 i - n 和 i + n，
    // 其中 n 为二维数组的列数。
    // 这样，对于 m x n 的二维数组，我们可以写一个函数来生成它的 neighbor 索引映射：

    /**
     * m x n 的二维数组，生成它的 neighbor 索引映射
     *
     * @param m 二维数组的行
     * @param n 二维数组的列
     * @return
     */
    public int[][] generateNeighborMapping(int m, int n) {
        int[][] neighbor = new int[m * n][];
        for (int i = 0; i < m * n; i++) {
            List<Integer> neighbors = new ArrayList<>();
            // 如果不是第一列，有左侧邻居
            if (i % n != 0) {
                neighbors.add(i - 1);
            }
            // 如果不是最后一列，有右侧邻居
            if (i % n != n - 1) {
                neighbors.add(i + 1);
            }
            // 如果不是第一行，有上方邻居
            // i - n代表的是当前单元格正上方单元格的索引。
            // 这是由于在编号时，同一列中上方单元格的编号比当前单元格的编号小n（n为列数）。
            // 例如在上述 3 行 4 列的网格里，单元格 5 正上方的单元格是 1，而5 - 4 = 1。
            // i - n >= 0用于判断上方单元格是否存在。要是i - n小于 0，就意味着当前单元格处于第一行，不存在上方单元格。
            // 例如，对于单元格 0，0 - 4 = -4 < 0，这表明它没有上方单元格。
            if (i - n >= 0) {
                neighbors.add(i - n);
            }
            // 如果不是最后一行，有下方邻居
            if (i + n < m * n) {
                neighbors.add(i + n);
            }
            // Java语言特性，将List类型转为int[]数组
            neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
        }
        return neighbor;
    }

    // 773.滑动谜题
    static class SlidingPuzzle {
        public int slidingPuzzle(int[][] board) {
            String target = "123450";
            // 将2x3的数组转化成字符串作为BFS的起点
            String start = "";
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    start = start + board[i][j];
                }
            }

            // ****** BFS 算法框架开始 ******
            Queue<String> queue = new LinkedList<>();
            HashSet<String> visited = new HashSet<>();
            // 从起点开始BFS搜索
            queue.offer(start);
            visited.add(start);

            int step = 0;
            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    String cur = queue.poll();
                    // 判断是否达到目标局面
                    if (target.equals(cur)) {
                        return step;
                    }
                    // 将数字0和相邻的数字交换位置
                    for (String neighborBoard : getNeighbors(cur)) {
                        // 防止走回头路
                        if (!visited.contains(neighborBoard)) {
                            queue.offer(neighborBoard);
                            visited.add(neighborBoard);
                        }
                    }
                }
                step++;
            }
            // ****** BFS算法 ******
            return -1;
        }

        List<String> getNeighbors(String board) {
            // 记录一维字符串的相邻索引
            int[][] mapping = new int[][]{{1, 3}, {0, 4, 2}, {1, 5}, {0, 4}, {3, 1, 5}, {4, 2}};
            int idx = board.indexOf('0');
            List<String> neighbors = new ArrayList<>();
            for (int adj : mapping[idx]) {
                String new_board = swap(board.toCharArray(), adj, idx);
                neighbors.add(new_board);
            }
            return neighbors;
        }

        String swap(char[] chars, int i, int j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            return new String(chars);
        }

        // 上述的mapping数组，如果是m x n怎么办
        int[][] generateNeighborMapping(int m, int n) {
            int[][] neighbor = new int[m * n][];
            for (int i = 0; i < m * n; i++) {
                List<Integer> neighbors = new ArrayList<>();
                // 如果不是第一列，有左侧邻居
                if (i % n != 0) {
                    neighbors.add(i - 1);
                }
                // 如果不是最后一列，有右侧邻居
                if (i % n != n - 1) {
                    neighbors.add(i + 1);
                }
                // 如果不是第一行，有上方邻居
                if (i - n >= 0) {
                    neighbors.add(i - n);
                }
                // 如果不是最后一行，有下方邻居
                if (i + n < m * n) {
                    neighbors.add(i + n);
                }
                // 将List类型转化为int[]数组
                neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
            }
            return neighbor;
        }
    }

    // 752. 解开密码锁的最少次数
    // 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
    // 每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
    // 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
    // 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
    // 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
    // 示例 1:
    // 输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
    // 输出：6
    // 解释：
    // 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
    // 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
    // 因为当拨动到 "0102" 时这个锁就会被锁定。
    static class OpenLock {
        public int openLock(String[] deadends, String target) {
            // 记录需要跳过死亡密码
            Set<String> deads = new HashSet<>();
            for (String s : deadends) {
                deads.add(s);
            }
            if (deads.contains("0000")) {
                return -1;
            }

            // 记录已经穷举过的密码，防止走回头路
            Set<String> visited = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            // 从起点开始启动广度优先搜索
            int step = 0;
            queue.offer("0000");
            visited.add("0000");

            while (!queue.isEmpty()) {
                int sz = queue.size();
                // 将当前队列中的所有节点向四周扩散
                for (int i = 0; i < sz; i++) {
                    String cur = queue.poll();
                    // 判断是否到达终点
                    if (cur.equals(target)) {
                        return step;
                    }
                    // 将一个节点的合法相邻节点加入队列
                    for (String neighbor : getNeighbors(cur)) {
                        if (!visited.contains(neighbor) && !deads.contains(neighbor)) {
                            queue.offer(neighbor);
                            visited.add(neighbor);
                        }
                    }
                }
                // 在这里增加步数
                step++;
            }
            // 如果穷举完都没有找到目标密码，那就是找不到了
            return -1;
        }

        // 将s的每一位向上拨动一次或向下拨动一次，8种相邻密码
        List<String> getNeighbors(String s) {
            List<String> neighbors = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                neighbors.add(plusOne(s, i));
                neighbors.add(minusOne(s, i));
            }
            return neighbors;
        }

        // 将s[j] 向上拨动一次
        String plusOne(String s, int j) {
            char[] ch = s.toCharArray();
            if (ch[j] == '9') {
                ch[j] = '0';
            } else {
                ch[j] += 1;
            }
            return new String(ch);
        }

        // 将s[j]向下拨动一次
        String minusOne(String s, int j) {
            char[] ch = s.toCharArray();
            if (ch[j] == '0') {
                ch[j] = '9';
            } else {
                ch[j] -= 1;
            }
            return new String(ch);
        }
    }

    /**
     * 662. 二叉树最大宽度
     * 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
     * 树的 最大宽度 是所有层中最大的 宽度 。
     * 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
     * 题目数据保证答案将会在  32 位 带符号整数范围内。
     * 示例一：
     * 输入：root = [1,3,2,5,3,null,9]
     * 输出：4
     * 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
     * 示例二：
     * 输入：root = [1,3,2,5,null,null,9,6,null,7]
     * 输出：7
     * 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
     * 示例三：
     * 输入：root = [1,3,2,5]
     * 输出：2
     * 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
     */
    static class WidthOfBinaryTree1 {
        // 这道题的解题关键是要给二叉树节点按行进行编号，然后你就可以通过每一行的最左侧节点和最右侧节点的编号推算出这一行的宽度，进而算出最大宽度：

        static class Pair {
            TreeNode node;
            int id;

            public Pair(TreeNode node, int id) {
                this.node = node;
                this.id = id;
            }
        }

        // 层序遍历（BFS）
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            // 记录最大的宽度
            int maxWidth = 0;
            // 标准BFS层序遍历解法
            Queue<Pair> queue = new LinkedList<>();
            queue.offer(new Pair(root, 1));
            // 从上到下遍历整棵树
            while (!queue.isEmpty()) {
                int sz = queue.size();
                int start = 0;
                int end = 0;
                // 从左到右遍历每一行
                for (int i = 0; i < sz; i++) {
                    Pair cur = queue.poll();
                    TreeNode curNode = cur.node;
                    int curId = cur.id;
                    // 记录当前行第一个和最后一个节点的编号
                    // 这里i==0获取第一个元素，其实就是left的最左的元素的id
                    if (i == 0) {
                        start = curId;
                    }
                    // 这里i == sz - 1获取最后一个元素，其实就是right的最右的元素的id
                    if (i == sz - 1) {
                        end = curId;
                    }
                    // 左右子节点入队，同时记录对应节点的编号
                    if (curNode.left != null) {
                        queue.offer(new Pair(curNode.left, curId * 2));
                    }
                    if (curNode.right != null) {
                        queue.offer(new Pair(curNode.right, curId * 2 + 1));
                    }
                }
                // 用当前行的宽度更新最大宽度
                maxWidth = Math.max(maxWidth, end - start + 1);
            }
            return maxWidth;
        }
    }
    static class WidthOfBinaryTree2 {
        // DFS(深度优先)
        ArrayList<Integer> firstId = new ArrayList<>();
        int maxWidth = 1;

        public int widthOfBinaryTree2(TreeNode root) {
            if (root == null) {
                return 0;
            }
            traverse(root, 1, 1);
            return maxWidth;
        }

        // 二叉树的遍历函数
        void traverse(TreeNode root, int id, int depth) {
            printIndent(count++);
            System.out.printf(" val = %d, id = %d, depth = %d\n", root == null? null : root.val, id, depth);
            if (root == null) {
                printIndent(--count);
                System.out.println("return");
                return;
            }
            if (firstId.size() == depth - 1) {
                // 因为代码是先 traverse(root.left) 后 traverse(root.right)，
                // 所以第一次到达这个深度一定是最左侧的节点，记录其编号
                firstId.add(id);
            } else {
                // 这个深度的其他节点，负责计算更新当前深度的最大宽度
                maxWidth = Math.max(maxWidth, id - firstId.get(depth - 1) + 1);
            }
            traverse(root.left, id * 2, depth + 1);
            traverse(root.right, id * 2 + 1, depth + 1);
        }

        int count = 0;
        void printIndent(int n) {
            for (int i = 0; i < n; i++) {
                System.out.print("   ");
            }
        }

        // 【重要】根据数组构建二叉树
        public static TreeNode buildTree(Integer[] array){
            if (array == null || array.length == 0){
                return null;
            }
            // 创建根节点
            TreeNode root = new TreeNode(array[0]);
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int index = 1; // 从数组第二个元素开始处理
            while(!queue.isEmpty() && index < array.length){
                TreeNode current = queue.poll();
                // 处理左子节点
                if (index < array.length && array[index] != null){
                    current.left = new TreeNode(array[index]);
                    queue.offer(current.left);
                }
                index++;

                // 处理右子节点
                if (index < array.length && array[index] != null){
                    current.right = new TreeNode(array[index]);
                    queue.offer(current.right);
                }
                index++;
            }
            return root;
        }

        public static void main(String[] args) {
            Integer[] rootArray = {1, 3, 2, 5, 3, null, 9};
            TreeNode root = buildTree(rootArray);
            // 此时root即为题目所需的二叉树根节点
            new WidthOfBinaryTree2().widthOfBinaryTree2(root);
            System.out.println("二叉树初始化完成，根节点值为：" + root.val);
        }
    }
}


